#pragma once

#include <cmath> 
#include <algorithm> 
#include <string>  
#include <vector>
#include <map>

using namespace std;

struct point{
	int x; int y;
};

struct segment{
	point begin;
	point end;
	segment(int beginx, int beginy, int endx, int endy) {
		begin.x = beginx;
		begin.y = beginy;
		end.x = endx;
		end.y = endy;
	}
};

segment get_middle_segment(segment processing_segment, const vector<int> &first_sequence, const vector<int> &second_sequence, int& shortest_edit_seq_length){
	int x, y;
	int n = processing_segment.end.x - processing_segment.begin.x;
	int m = processing_segment.end.y - processing_segment.begin.y;
	vector<int> max_advance1(4 * (n + m), 0);
	int* max_advance = &max_advance1[2 * (n + m)];
	vector<int> max_reverse_advance1(4 * (n + m), n);
	int* max_reverse_advance = &max_reverse_advance1[2 * (n + m)];

	int delta = n - m;

	for (int advance = 0; advance <= (m + 1 + n) / 2; advance++){
		for (int diag_no = -advance; diag_no <= advance; diag_no += 2){
			if ((diag_no == -advance) || (diag_no != advance && max_advance[diag_no - 1] < max_advance[diag_no + 1])){
				x = max_advance[diag_no + 1];
			}
			else{
				x = max_advance[diag_no - 1] + 1;
			}
			y = x - diag_no;
			while (x < n && y < m && first_sequence[processing_segment.begin.x + x + 1] == second_sequence[processing_segment.begin.y + y + 1]){
				x++, y++;
			}
			max_advance[diag_no] = x;
			if (diag_no == 0 && x >= n && y >= m){
				shortest_edit_seq_length = 0;
				return segment(0, 0, n, m);
			}
			if ((delta + 1) % 2 == 0 && abs(diag_no - delta) <= abs(advance - 1) && max_advance[diag_no] >= max_reverse_advance[diag_no]){
				segment middle_segment(max_advance[diag_no], max_advance[diag_no] - diag_no, x, y);
				while (x < n && y < m && first_sequence[processing_segment.begin.x + middle_segment.begin.x + 1] == second_sequence[processing_segment.begin.y + middle_segment.begin.y + 1]){
					middle_segment.begin.x++; middle_segment.begin.y++;
				}
				shortest_edit_seq_length = 2 * advance - 1;
				return middle_segment;
			}
		}

		for (int diag_no = -advance; diag_no <= advance; diag_no += 2){
			if ((diag_no == advance) || (diag_no != -advance && max_reverse_advance[delta + diag_no - 1] < max_reverse_advance[delta + diag_no + 1])){
				x = max_reverse_advance[delta + diag_no - 1];
			}
			else{
				x = max_reverse_advance[delta + diag_no + 1] - 1;
			}
			y = x - (diag_no + delta);
			while (x > 0 && y > 0 && first_sequence[processing_segment.begin.x + x] == second_sequence[processing_segment.begin.y + y]){
				x--, y--;
			}
			max_reverse_advance[diag_no + delta] = x;
			if (delta % 2 == 0 && abs(diag_no + delta) <= abs(advance) && max_advance[diag_no + delta] >= max_reverse_advance[diag_no + delta]){
				segment middle_segment(max_reverse_advance[diag_no + delta], max_reverse_advance[diag_no + delta] - (diag_no + delta), x, y);
				while (middle_segment.end.x > 0 && middle_segment.end.y > 0 &&
					first_sequence[processing_segment.begin.x + middle_segment.end.x] == second_sequence[processing_segment.begin.y + middle_segment.end.y]){
					middle_segment.end.x--, middle_segment.end.y--;
				}
				shortest_edit_seq_length = 2 * advance;
				return middle_segment;
			}
		}
	}
	return segment(0, 0, 0, 0);
}

int get_lcs(segment processing_segment, const vector<int> &first_sequence, const vector<int> &second_sequence, vector<int> &result){
	int first_subsequence_length = processing_segment.end.x - processing_segment.begin.x;
	int second_subsequence_length = processing_segment.end.y - processing_segment.begin.y;
	if (first_subsequence_length == 0 || second_subsequence_length == 0){
		return max(first_subsequence_length, second_subsequence_length);
	}

	int shortest_edit_seq_length = 0;
	segment middle_segment = get_middle_segment(processing_segment, first_sequence, second_sequence, shortest_edit_seq_length);

	if (shortest_edit_seq_length > 1){
		segment next_segment(processing_segment.begin.x, processing_segment.begin.y,
			processing_segment.begin.x + middle_segment.begin.x, processing_segment.begin.y + middle_segment.begin.y);
		get_lcs(next_segment, first_sequence, second_sequence, result);
		for (int i = processing_segment.begin.x + middle_segment.begin.x + 1; i <= processing_segment.begin.x + middle_segment.end.x; ++i){
			result.push_back(first_sequence[i]);
		}
		next_segment = segment(processing_segment.begin.x + middle_segment.end.x, processing_segment.begin.y + middle_segment.end.y,
			processing_segment.end.x, processing_segment.end.y);
		get_lcs(next_segment, first_sequence, second_sequence, result);
	}
	else{
		if (second_subsequence_length > first_subsequence_length){
			for (int i = processing_segment.begin.x + 1; i <= processing_segment.begin.x + first_subsequence_length; i++){
				result.push_back(first_sequence[i]);
			}
		}
		else {
			for (int i = processing_segment.begin.y + 1; i <= processing_segment.begin.y + second_subsequence_length; i++){
				result.push_back(second_sequence[i]);
			}
		}
	}
	return (first_subsequence_length + second_subsequence_length - shortest_edit_seq_length) / 2;
}

vector<int> get_lcs(const vector<int> &first_int_sequence, const vector<int> &second_int_sequence) {
	segment whole_sequences(-1, -1, first_int_sequence.size() - 1, second_int_sequence.size() - 1);
	vector<int> longest_common_sequence;
	get_lcs(whole_sequences, first_int_sequence, second_int_sequence, longest_common_sequence);
	return longest_common_sequence;
}

void get_hash(const vector<string>& string_sequence, map<int, string>& int_map, map<string, int>& string_map, int &max_hash) {
	for (const auto& string : string_sequence) {
		if (!string_map.count(string)){ 
			string_map[string] = ++max_hash;
			int_map[max_hash] = string;
		}
	}
}

vector<int> digitize(const vector<string>& string_sequence, map<string, int>& string_map) 
{
	vector<int> result;
	for (int i = 0; i<(int)string_sequence.size(); ++i) {
		int int_hash = string_map[string_sequence[i]];
		result.push_back(int_hash);
	}
	return result;
}

vector<string> get_lcs_string(const vector<string>& first_string_sequence, const vector<string>& second_string_sequence) {
	vector<int> first_int_sequence;
	vector<int> second_int_sequence;
	map<int, string> int_map;
	map<string, int> string_map;

	int max_hash = -1;
	get_hash(first_string_sequence, int_map, string_map, max_hash);
	get_hash(second_string_sequence, int_map, string_map, max_hash);

	first_int_sequence = digitize(first_string_sequence, string_map);
	second_int_sequence = digitize(second_string_sequence, string_map);

	vector<int> lcs_int = get_lcs(first_int_sequence, second_int_sequence);

	vector<string> result;
	for (int index : lcs_int) {
		result.push_back(int_map[index]);
	}
	return result;
}

